'''
https://leetcode.cn/problems/partition-labels
'''
from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        first_position = [-1] * 26
        res = []
        for i, c in enumerate(s):
            idx = ord(c) - ord('a')
            first_appear = first_position[idx]
            if first_appear == -1:
                res.append([i, 1])
                first_position[idx] = i
            else:
                while res[-1][0] > first_appear:
                    res.pop()
                res[-1][1] = i - res[-1][0] + 1
        return [a for _, a in res]
    
    def partitionLabels2(self, s: str) -> List[int]:
        last_position = {c:i for i, c in enumerate(s)}
        res = []
        begin = -1
        last = 0
        for i, c in enumerate(s):
            last = max(last, last_position[c])
            if i == last:
                res.append(i - begin)
                begin = i
        return res


s = "ababcbacadefegdehijhklij"
print(Solution().partitionLabels2(s))